package com.hanlin.day04;

/**
 * 描述：链表相加 （中度）
 * https://leetcode.cn/problems/add-two-numbers/
 *
 * @author:hl.yuan
 * @date:2022-06-19
 */
public class LinkedListAdd {


    public static class ListNode {
        public ListNode next;
        public int val;

        public ListNode(Integer value) {
            this.val = value;
        }
    }

    /**
     * 链表相加
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 链表长度
        int listLength1 = listLength(l1);
        int listLength2 = listLength(l2);
        // 得到那个链表长
        ListNode l = listLength1 > listLength2 ? l1 : l2;
        ListNode s = listLength1 > listLength2 ? l2 : l1;

        ListNode curL = l;
        ListNode curs = s;
        ListNode last = curL;
        // 进位
        int carry = 0;
        // 余数
        int curNum = 0;
        // 先迭代短链表
        while (curs != null) {
            curNum = curL.val + curs.val + carry;
            curL.val = (curNum % 10);
            carry = (curNum / 10);
            last = curL;
            curL = curL.next;
            curs = curs.next;
        }

        while (curL != null) {
            // 当前值加上进位信息
            curNum = curL.val + carry;
            curL.val = (curNum % 10);
            carry = (curNum / 10);
            last = curL;
            curL = curL.next;
        }
        // 前面两个循环后，进位信息还有，说明有数据，这里需要添加一个
        if (carry != 0) {
            last.next = new ListNode(1);
        }

        return l;
    }

    /**
     * 获取链表长度
     *
     * @param node 链表
     * @return 返回长度
     */
    public static int listLength(ListNode node) {
        int count = 0;
        while (node != null) {
            count++;
            node = node.next;
        }
        return count;
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        l1.next.next.next = new ListNode(9);
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(7);

        addTwoNumbers(l1,l2);
    }

}
